#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <set>
using namespace std;
class UF
{
public:
    UF(int N)
    {
        parents = new int[N + 1];
        fill(parents, parents + N + 1, -1);
        size = new int[N + 1];
        fill(size, size + N + 1, 1);
    }
    int par(int x)
    {
        if (parents[x] = -1)
            return x;
        int p = par(parents[x]);
        parents[x] = p;
        return p;
    }
    void Union(int x, int y)
    {
        int parx = par(x), pary = par(y);
        if (parx == pary)
            return;
        if (size[parx] < size[pary])
        {
            parents[parx] = pary;
            size[pary] += size[parx];
        }
        else
        {
            parents[pary] = parx;
            size[parx] += size[pary];
        }
    }
    bool isSameClass(int x, int y) { return par(x) == par(y); };
    int *parents, *size;
};
class Solution
{
public:
    void sortStr(vector<int> arr, string &s)
    {
        vector<int> alphabet(26, 0);
        for (int i : arr)
        {
            alphabet[s[i] - 'a']++;
        }
        for (int j = 0, i = 0; j < arr.size(); ++j)
        {
            for (i = 0; i < 26; ++i)
            {
                if (alphabet[i] != 0)
                    break;
            }
            s[arr[j]] = i + 'a';
            alphabet[i] -= 1;
        }
    }
    string smallestStringWithSwaps(string s, vector<vector<int>> &pairs)
    {
        vector<set<int>> unions(s.size());
        UF uf(s.size() - 1);
        for (auto &it : pairs)
        {
            uf.Union(it[0], it[1]);
        }
        for (auto &it : pairs)
        {
            unions[uf.par(it[0])].insert(it[0]);
            unions[uf.par(it[0])].insert(it[1]);
        }
        for (auto &u : unions)
        {
            if (u.size() <= 1)
                continue;
            vector<int> arr(u.begin(), u.end());
            sortStr(arr, s);
        }
        return s;
    }
};